package com.wyw.leetcode.learning.medium;

import java.util.Arrays;

/**
 * leetcode topic 567
 * 字符串的排列
 *
 * @Author Mr Wu （yewen.wu.china@gmail.com）
 * @Date 2021/11/15 13:48
 */
public class Topic567 {
    public static void main(String[] args) {
        String s1 = "ab";
        String s2 = "cbcacb";
//        String s2 = "eidbaooo";
        System.out.println(checkInclusion(s1, s2));
        System.out.println(checkInclusion1(s1, s2));
        System.out.println(checkInclusion2(s1, s2));
    }

    /**
     *
     * @param s1    子串
     * @param s2    长串
     * @return      有无
     */
    public static boolean checkInclusion(String s1, String s2) {
        int[] arr1 = new int[26];
        int[] arr2 = new int[26];

        int lengths1 = s1.length();
        int lengths2 = s2.length();
        if(lengths1 > lengths2) {
            return  false;
        }

        for(int i = 0; i< lengths1; i++) {
            ++arr1[s1.charAt(i) - 'a'];
            ++arr2[s2.charAt(i) - 'a'];
        }
        if(Arrays.equals(arr1, arr2)) {
            return true;
        }

        for(int i = lengths1; i < lengths2; i++) {
            ++arr2[s2.charAt(i) - 'a'];
            --arr2[s2.charAt(i - lengths1) - 'a'];
            if(Arrays.equals(arr1, arr2)) {
                return true;
            }
        }
        return false;
    }
    /**
     *
     * @param s1    子串
     * @param s2    长串
     * @return      有无
     */
    public static boolean checkInclusion1(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        if (n > m) {
            return false;
        }
        int[] cnt = new int[26];
        for (int i = 0; i < n; ++i) {
            --cnt[s1.charAt(i) - 'a'];
            ++cnt[s2.charAt(i) - 'a'];
        }
        int diff = 0;
        for (int c : cnt) {
            if (c != 0) {
                ++diff;
            }
        }
        if (diff == 0) {
            return true;
        }
        for (int i = n; i < m; ++i) {
            int x = s2.charAt(i) - 'a', y = s2.charAt(i - n) - 'a';
            if (x == y) {
                continue;
            }
            if (cnt[x] == 0) {
                ++diff;
            }
            ++cnt[x];
            if (cnt[x] == 0) {
                --diff;
            }
            if (cnt[y] == 0) {
                ++diff;
            }
            --cnt[y];
            if (cnt[y] == 0) {
                --diff;
            }
            if (diff == 0) {
                return true;
            }
        }
        return false;
    }
    /**
     *
     * @param s1    子串
     * @param s2    长串
     * @return      有无
     */
    public static boolean checkInclusion2(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        if (n > m) {
            return false;
        }
        int[] cnt = new int[26];
        for (int i = 0; i < n; ++i) {
            --cnt[s1.charAt(i) - 'a'];
        }
        int left = 0;
        for (int right = 0; right < m; ++right) {
            int x = s2.charAt(right) - 'a';
            ++cnt[x];
            while (cnt[x] > 0) {
                --cnt[s2.charAt(left) - 'a'];
                ++left;
            }
            if (right - left + 1 == n) {
                return true;
            }
        }
        return false;
    }
}
